// GAURAV DESHMUKH



#include<iostream.h>
#include<stdlib.h>
#include<conio.h>

class node
{
	int data;
	class node *next;

	public:
	friend class linklist;
};

class linklist
{
	class node *head;

	public:
	linklist()
	{
		head=new(node);
		head->data=0;
		head->next=NULL;
	}

	void create(void);
	void display(void);
	void inspos(void);
	void insdata(void);
	void delpos(void);
	void deldata(void);
	void sort_data(void);
	void sort_link(void);
	void reverse(void);
	void concat(void);
	void merge(void);
	void length(void)
	{
		cout<<"\n\nTHE LENGTH OF LIST IS:-\t"<<head->data;
	}
};
int main(void)
{
	int chmnu;
	class linklist list1;

	while(1)
	{
		clrscr();
		cout<<"\n\n1.CREATE LINK LIST\n2.DISPLAY DATA\n";
		cout<<"3.INSERT BY POSITION\n4.INSERT BY DATA\n";
		cout<<"5.DELETE BY POSITION\n6.DELETE BY DATA";
		cout<<"\n7.SORTING BY DATA\n8.SORTING BY LINK\n";
		cout<<"9.REVERSE LIST\n10.LENGTH OF LIST\n11.CONCATINATE";
		cout<<"\n12.MERGING OF LISTS\n\n13.EXIT";

		cout<<"\n\n\nEnter Your Choice:-\t";
		cin>>chmnu;

		switch(chmnu)
		{
			case 1: clrscr();
					list1.create();
					break;

			case 2: list1.display();
					break;

			case 3: list1.inspos();
					break;

			case 4: list1.sort_data();
					clrscr();
					list1.insdata();
					break;

			case 5:	list1.delpos();
					break;

			case 6: list1.deldata();
					break;

			case 7: list1.sort_data();
					break;

			case 8: list1.sort_link();
					break;

			case 9: list1.reverse();
					break;

			case 10:list1.length();
					break;

			case 11:list1.concat();
					break;

			case 12:list1.sort_data();
					clrscr();
					list1.merge();
					break;

			case 13:return 0;
			default: cout<<"\n\n\n\aERROR !!!  FALSE INPUT ENCOUNTERED";
		}

		getch();
	}
}
//*********CREATING A LINK LIST****************
void linklist::create(void)
{
	char chcreate='n';
	class node *temp;

	//ALLOCATING MEMORY FOR A NEW LINK LIST
	temp=new(node);

	if(temp==NULL)
	{
		cout<<"\a\aNO MORE FREE SPACE AVAILABLE";
		exit(0);
	}
	head->next=temp;

	do
	{
		head->data++;
		cout<<"\n\nENTER DATA:-\t";
		cin>>temp->data;
		temp->next=NULL;

		cout<<"\n\nWANNA ADD NEW DATA(y/n):-\t";
		cin>>chcreate;

		if(chcreate=='y')
		{
			temp->next=new(node);
			temp=temp->next;
			temp->next=NULL;
		}

	}while(chcreate=='y');

}

//*********************DISPLAY LINK LIST**********************
void linklist::display(void)
{
	int cnt=0;
	class node *disnode;

	disnode=head->next;

	if(head->next==NULL)
	{
		cout<<"\n\nTHE LINK LIST IS EMPTY!!";

		goto enddis;
	}
	cout<<"\n\nTHE DATA IN THE LIST ARE:-\n\n";
	do
	{
		if(cnt==0)
		{
			cout<<"0. THIS NODE	IS HEAD NODE\n\n";
			cnt++;
			continue;
		}
		else
			cout<<cnt<<". "<<disnode->data<<"\n";
		cnt++;
		disnode=disnode->next;

	}while(disnode!=NULL);

	enddis:
}

//***************INSERT BY POSITION***********
void linklist::inspos()
{

	int i,chadd,datanum;
	class node *retadd,*cngnode,*temp,*adnode;

	adnode=head->next;

	if(head->next==NULL)
	{
		clrscr();
		goto front;
	}

	while(1)
	{
		cngnode=adnode;

		clrscr();

		cout<<"\t\t\t       A D D\tD A T A\t";
		cout<<"\n\n1.INSERT IN THE LIST\n2.DISPLAY DATA\n3.BACK TO MAIN MENU";
		cout<<"\n\nEnter Your Choice:-\t";
		cin>>chadd;

		switch(chadd)
		{

			//ADD AT ANY POSITION
			case 1: backadd:
				clrscr();
				display();
				cngnode=adnode;


				cout<<"\n\nENTER THE NUMBER AFTER WHICH YOU WANT TO ENTER THE DATA:-\t";
				cin>>datanum;

				if(datanum<0 || datanum>head->data)
				{
					cout<<"\n\n\n\aERROR !!!  FALSE INPUT ENCOUNTERED";
					cout<<"\n\n\n	press any key to continue";
					getch();
					goto backadd;
				}

				if(datanum==0)
					goto front;

				temp=new(node);

				cout<<"\n\nENTER THE DATA:-\t";
				cin>>temp->data;
				cout<<"\n\nDATA IS ADDED";

				for(i=0;i<datanum-1;i++)
					cngnode=cngnode->next;

				retadd=cngnode->next;
				temp->next=retadd;
				cngnode->next=temp;
				head->data++;
				break;

			case 2: display();
				break;

			case 3: goto endinspos;

			default: cout<<"\n\n\n\aERROR ENCOUNTERED!!!  FALSE INPUT ENTERED";
				 break;


			//ADD AT FRONT
				front:

				cout<<"\n\nENTER THE DATA:-\t";
				temp=new(node);
				cin>>temp->data;
				cout<<"\n\nDATA IS ADDED";


				head->next=temp;
				temp->next=adnode;
				adnode=temp;
				head->data++;
				break;

		}
		getch();
	}
	endinspos:
}

//*************INSERT BY DATA************
void linklist::insdata()
{
	int datains;
	class node *temp,*prev;

	cout<<"ENTER DATA TO BE ADDED:-\t";
	cin>>datains;

	temp=head->next;
	prev=head;

	while(temp->data<datains && temp!=NULL)
	{
		prev=temp;
		temp=temp->next;
	}
	prev->next=new(node);
	(prev->next)->data=datains;
	(prev->next)->next=temp;
	head->data++;
	cout<<"\n\nDATA IS ADDED";
}


//*********************DELETE DATA FROM A LINK LIST****************
void linklist::delpos()
{
	int i,chdel,datanum;
	class node *retdel,*cngnode,*temp,*delnode;

	delnode=head->next;

	while(1)
	{
		clrscr();
		if(head->data==0)
		{
			head->next=NULL;
			cout<<"\aTHE LIST IS EMPTY NOW !!!PRESS ENTER TO CONTINUE!";
			goto enddelpos;
		}

		cngnode=delnode;

		cout<<"\t\t\t       D E L E T E\tD A T A\t";
		cout<<"\n\n1.DELETE FROM THE LIST\n2.DISPLAY DATA\n3.EXIT TO MAIN MENU";

		cout<<"\n\nEnter Your Choice:-\t";
		cin>>chdel;

		switch(chdel)
		{

			//DELETE AT ANY POSITION
			case 1: backdel:
				clrscr();

				display();


				cout<<"\n\nENTER THE NUMBER OF NODE WHICH YOU WANT TO DELETE:-\t";
				cin>>datanum;

				if(datanum==0)
				{
					cout<<"\n\n\aSORRY, WITH THE HEAD NODE USER'S INTERFERENCE ISN'T ALLOWED!!!!";
					cout<<"\n\n\n	press any key to continue";
					getch();

					goto backdel;
				}
				if(datanum<0 || datanum>head->data)
				{
					cout<<"\n\n\n\aERROR !!!  FALSE INPUT ENCOUNTERED";
					cout<<"\n\n\n	press any key to continue";
					getch();

					goto backdel;
				}

				head->data--;
				if(datanum==1)
					goto del;

				for(i=0;i<datanum-1;i++)
				{
					retdel=cngnode;
					cngnode=cngnode->next;
					temp=cngnode->next;
				}
				cout<<"\n\nTHE DATA BEING DELETED IS:-\t"<<cngnode->data;
				delete(cngnode);
				retdel->next=temp;
				break;

			case 2: display();
				break;

			case 3: goto enddelpos;
			default: cout<<"\n\n\n\aERROR ENCOUNTERED!!!  FALSE INPUT ENTERED";
				 break;


			//DELETE AT FRONT
			del:
				head->next=delnode->next;
				cout<<"\n\nTHE DATA BEING DELETED IS:-\t"<<delnode->data;
				delnode=delnode->next;
				delete(cngnode);
				break;

		}
		getch();
	}
	enddelpos:
	cout<<"\n\nPRESS ANY KEY NOW";
}
//****************DELETE BY DATA***********
void linklist::deldata()
{
	int datadel;
	class node *prev,*temp,*succ;
	clrscr();

	if(head->next!=NULL)
	{
		cout<<"ENTER DATA TO BE DELETED:-\t";
		cin>>datadel;

		prev=head;
		temp=head->next;
		succ=temp->next;

		while(temp->data!=datadel && temp->next!=NULL)
		{
			prev=temp;
			temp=temp->next;
			succ=temp->next;
		}

		if(temp->data==datadel)
		{
			prev->next=succ;
			cout<<"\n\nDATA IS DELETED";
			delete(temp);
			head->data--;
		}
		else
			cout<<"\n\nNO SUCH DATA PRESENT";

		if(head->data==0)
			head->next=NULL;
	}
	else
	{
		cout<<"\n\nTHE LINK LIST IS EMPTY";
	}
}

//*******************SORTING BY LINK**********
void linklist::sort_link()
{
	int m,n,dif;
	int ex=head->data;
	class node *compnode,*prev,*succed,*present,*temp;

	clrscr();
	if(head->next==NULL)
	{
		cout<<"THE LIST IS EMPTY";
		goto endsrtlink;
	}
	cout<<"\n\nUNSORTED LIST:-\n\n";

	display();

	//BUBBLE SORT
	for(m=0;m<ex-1;m++)
	{
		present=head->next;
		compnode=present->next;

		for(n=0;n<ex-m-1;n++)
		{
			temp=present;
			succed=compnode->next;

			if(present->data>compnode->data)
			{
				present->next=succed;

				if(n==0)
					head->next=compnode;
				else
					prev->next=compnode;

				compnode->next=present;
				temp=compnode;
				prev=compnode;
			}

			else//if swap does not takes place
			{
				prev=present;
				present=present->next;
			}
			compnode=present->next;

			if(n==0)
			   head->next=temp;
		}
	}
	cout<<"\n\nSORTED LIST:-\n\n";
	display();
	cout<<"\n\n\n\aTHE LIST IS SORTED NOW";
	endsrtlink:
}



//********************SORTING BY DATA************************
void linklist::sort_data()
{
	int m,n,dif,ex=head->data;
	class node *temp,*cngnode,*srtnode;

	clrscr();
	if(head->next==NULL)
	{
		cout<<"THE LIST IS EMPTY";
		goto endsrtdata;
	}

	cout<<"\n\nUNSORTED LIST:-\n\n";

	display();

	cngnode=head->next;
	srtnode=cngnode;

	for(m=0;m<ex-1;m++)
	{
		for(n=0;n<ex-m-1;n++)
		{

			if(srtnode->data > (srtnode->next)->data)
			{
				temp->data=srtnode->data;
				srtnode->data=(srtnode->next)->data;
				(srtnode->next)->data=temp->data;
			}
			srtnode=srtnode->next;
		}
		srtnode=cngnode;
	}

	cout<<"\n\nSORTED LIST:-\n\n";
	display();
	cout<<"\n\n\nTHE LIST IS SORTED NOW";
	endsrtdata:
}

//*********************REVERSING A LINK LIST***********************
void linklist::reverse()
{
	int cnt=0,temp;

	class node *retnode,*cgnode,*tmpnode,*revnode;

	clrscr();
	if(head->next==NULL)
	{
		cout<<"THE LIST IS EMPTY";
		goto endreverse;
	}

	display();

	revnode=head->next;
	retnode=revnode;
	cgnode=new(node);

	while(revnode!=NULL)
	{
		temp=revnode->data;

		revnode=revnode->next;

		if(cnt==0)
		  cgnode->next=NULL;


		else
		{
			cgnode=new(node);
			cgnode->next=tmpnode;
		}

		cgnode->data=temp;
		tmpnode=cgnode;
		cnt++;
	}

	while(retnode!=NULL)
	{
		revnode=retnode;
		retnode=retnode->next;
		delete(revnode);
	}

	cout<<"\n\nTHE REVRESED LIST IS:-";
	head->next=cgnode;
	display();
	cout<<"\n\n\n\aTHE LIST IS REVERSED NOW";

	endreverse:
}

//************CONCATINATION*****************
void linklist::concat()
{
	class node *temp;
	class linklist conky;

	clrscr();
	cout<<"ENTER THE FOLLOWING FOR 2nd NODE\n";
	conky.create();

	temp=head;

	while(temp->next!=NULL)
	{
		temp=temp->next;
	}
	temp->next=conky.head->next;
	clrscr();
	head->data=conky.head->data+head->data;
	cout<<"THE CONCATINATED LINK LIST IS:-\t";
	display();

	delete(conky.head);
}

//************MERGING OF LINK LISTS*****************
void linklist::merge()
{
	class node *fst1,*fst2,*prev1;
	class linklist conky;

	clrscr();
	cout<<"ENTER THE FOLLOWING FOR 2nd NODE\n";
	conky.create();


	while(conky.head->next!=NULL)
	{
		prev1=head;
		fst1=head->next;
		fst2=conky.head->next;

		while(fst1!=NULL)
		{
			if(fst2->data<fst1->data)
			{
				conky.head->next=fst2->next;
				prev1->next=fst2;
				fst2->next=fst1;
				goto endmerge;
			}
			prev1=fst1;
			fst1=fst1->next;
		}
		if(fst1==NULL)
		{
			conky.head->next=fst2->next;
			prev1->next=fst2;
			fst2->next=NULL;
		}
		endmerge:
		head->data++;
		conky.head->data--;
	}
	clrscr();
	cout<<"THE MERGED LINK LIST IS:-\t";
	display();

}




